package MiddlePractice;

public class Demo79 {
	
//	79. 单词搜索
//	给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
//
//	单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

	
	public boolean exist(char[][] board, String word) {
        
		for(int i=0; i<board.length; i++) {
			for(int j=0; j<board[0].length; j++) {
				
				if(board[i][j] != word.charAt(0)) {
					continue;
				}
				
				boolean[][] used = new boolean[board.length][board[0].length];
				used[i][j] = true;
				boolean res = backTrack(board, used, i, j, word, 1);
				if(res) return true;
				
			}
		}
		
		return false;
		
    }
	
	
	private boolean backTrack(char[][] board, boolean[][] used, int x, int y, String word, int i) {
		
		if(i == word.length()) {
			return true;
		}
		
		
		
		
		int[][] choices = new int[][] {{-1,0}, {1,0}, {0,-1}, {0,1}};
		
		for(int[] choice : choices) {
			int choiceX = choice[0] + x;
			int choiceY = choice[1] + y;
			if(choiceX < 0 || choiceY <0 || choiceX >= board.length || choiceY >= board[0].length) {
				continue;
			}
			
			if(used[choiceX][choiceY]) {
				continue;
			}
			
			if(board[choiceX][choiceY] == word.charAt(i)) {
				
				used[choiceX][choiceY] = true;
				boolean res = backTrack(board, used, choiceX, choiceY, word, i+1);
				if(res)	return true;
				used[choiceX][choiceY] = false;
			}
			
		}
		
		return false;
		
	}
	
}




